
"""
98. 验证二叉搜索树
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    """
     * 遍历二叉树：
     * 重点：二叉搜索树要求左节点所有子节点 < 根节点 < 所有右节点
     * 每次遍历传三个参数，根节点，左节点最小值，右节点最大值，判断大小即可
    """
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.traverse(root, None, None)

    def traverse(self, root: Optional[TreeNode], min: Optional[TreeNode], max: Optional[TreeNode]):
        """
        遍历二叉树
        @param root: 根节点
        @param min:  左节点最小值
        @param max: 右节点最小值
        @return: 结果
        """
        if not root:
            return True

        if min and min.val >= root.val:
            return False
        if max and max.val <= root.val:
            return False

        # 前序位置
        left = self.traverse(root.left, min, root)
        # 中序位置
        right = self.traverse(root.right, root, max)
        # 后序位置
        return left and right